package demo.DataStrucAndAlgo.Graph;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/30-07-30-15:30
 * @Description：demo.DataStrucAndAlgo.Graph   图结构
 */
/*
图
    多对多的关系
    顶点（vertex） 边（edge） 路径、无向图、有向图，带权图
    图的表现方式：邻接矩阵（两顶点直接相连，对应数组值为1，存在空间浪费）、邻接表（表示包含与该顶点直接相连的顶点）
    结构分析：
        顶点数据：Arraylist存储
        邻接矩阵：int[][]存储
        插入顶点  insertVertex
        插入边   insertEdges
        获取顶点树  getNumOfVertex
        获取边数    getNumOfEdges
        获取顶点值   getValueByIndex
        获取边权值   getWeight
        打印邻接矩阵    show
 */
public class Graph {
    private ArrayList<Character> vertexList;
    private int[][] edges;
    private int numOfEdge;
    public Graph(int num){
        vertexList = new ArrayList<>(num);
        edges = new int[num][num];
        numOfEdge = 0;
    }
    public void insertVertex(char vertex){
        vertexList.add(vertex);
    }

    /**
     * 无向图
     * @param v1       顶点1
     * @param v2     顶点2
     * @param weight    权值
     */
    public void insertEdges(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdge++;
    }
    public int getNumOfVertex(){
        return vertexList.size();
    }
    public int getNumOfEdge(){
        return numOfEdge;
    }
    public int getVertexByIndex(int index){
        return vertexList.get(index);
    }
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }
    public void show(){
        for (int i = 0; i < edges.length; i++) {
            System.out.println(Arrays.toString(edges[i]));
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(5);
        for (int i = 0; i < 5; i++) {
            graph.insertVertex((char)('A' + i));
        }
        //添加边：A-B,A-C,C-B,B-E,B-D
        graph.insertEdges(0,1,1);
        graph.insertEdges(0,2,1);
        graph.insertEdges(2,1,1);
        graph.insertEdges(1,4,1);
        graph.insertEdges(1,3,1);
        System.out.println("邻结矩阵为：");
        graph.show();
        System.out.println("A-B边权值为：");
        System.out.println(graph.getWeight(0,1));
        System.out.println("D顶点的数据为：" + (char)graph.getVertexByIndex(3));
        System.out.print("含有的边数位：" + graph.getNumOfEdge());
    }
}
